package com.top145;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution130 {
    public void solve(char[][] board) {
        boolean[][] visited = new boolean[board.length][board[0].length];
        LinkedList<int[]> queue = new LinkedList<>();
        for (int i = 0; i < board.length; i++) {
            if (board[i][0] == 'O') queue.add(new int[]{i, 0});
            if (board[i][board[0].length - 1] == 'O') queue.add(new int[]{i, board[0].length - 1});
        }
        for (int i = 1; i < board[0].length; i++) {
            if (board[0][i] == 'O') queue.add(new int[]{0, i});
            if (board[board.length - 1][i] == 'O') queue.add(new int[]{board.length - 1, i});
        }
        while (!queue.isEmpty()) {
            int[] node = queue.removeFirst();
            int i = node[0];
            int j = node[1];
            if (i - 1 >= 0 && board[i - 1][j] == 'O' && !visited[i - 1][j]) {
                visited[i - 1][j] = true;
                queue.add(new int[]{i - 1, j});
            }
            if (i + 1 < board.length && board[i + 1][j] == 'O' && !visited[i + 1][j]) {
                visited[i + 1][j] = true;
                queue.add(new int[] {i + 1, j});
            }
            if (j - 1 >= 0 && board[i][j - 1] == 'O' && !visited[i][j - 1]) {
                visited[i][j - 1] = true;
                queue.add(new int[] {i, j -1});
            }
            if (j + 1 < board[0].length && board[i][j + 1] == 'O' && !visited[i][j + 1]) {
                visited[i][j + 1] = true;
                queue.add(new int[] {i, j + 1});
            }
        }
        for (int i = 1; i < board.length - 1; i++) {
            for (int j = 1; j < board[0].length - 1; j++) {
                if (board[i][j] == 'O' && !visited[i][j]) board[i][j] = 'X';
            }
        }
    }
}
